Куркчі В'ячеслав Андрійович
kourktchi@ukrtop.com
магістрант групи ПЗ-99, ФОТІ
научний керівник:
Ладиженський Юрій Валентинович

тема магістерскої роботы:
Паралельні алгоритми для рішення задач на графах.

• Ладиженський Ю.В., Куркчі В.А. Паралельні алгоритми пошуку незалежних множин на графах.//Матеріали другої конференції "Донбас-2020".-2004, стр.609-616.   [pdf - російською] (215 кб)
       У статті наведені два паралельних еврістических алгоритми для пошуку найбільшої незалежної множини. Модифіковано алгоритм Голдберга-Спенсера. Розглянуто алгоритм, заснованний на базі жадної еврістики та обмеженого перебору. Наведені результати тестування обох алгоритмів, зроблено висновки що до їх точності.
  

• Куркчі В.А. Дослідження алгоритмів пошуку максимальних незалежних множин на графах. Студентська наукова робота (заохочувальний диплом всеукраїнського конкурса НДПС 2002г.)   [pdf - російською] (329 кб)
       В цій роботі представлені результати дослідження алгоритмів для находження максимальних незалежних множин вершин. Було розглянуто алгоритм Брона-Кербоша, та проведена його модифікація.
       Для перевірки еффективності роботы алгоритмів було розроблено програму на мові Visual C++ 6.0, проведено ряд експериментів та зроблено висновки що до еффективності модификацій алгоритма у порівнянні з орігіналом: показано, що отримані алгоритми витрачають на рішення меньше часу.
  

• Голдберг М., Спенсер Т. Паралельна побудова найбільшої незалежної множини. Переклад с англійскої Куркчі В.А. [pdf - російською] (208 кб)
       Розглянуто задачу паралельної побудови найбільшої незалежної множини даного графа. Подан новий детермінований NC-алгоритм для моделі EREW PRAM. Для графів с n вершинами и m ребрами він використовує O((n+m)/lgn) процесорів и закінчує роботу за час O(log³n), зменьшуючи в logn раз і час, і кількість використаних процесорів, у порівнянні з попередніми детерминованими алгоритмами, що розв'язують задачу, використовуючи линійну кількість процесорів.
  

• Goldberg M., Spenser T. Новий паралельний алгоритм для задачи о найбільшій незалежній множині [pdf - англійською] (189 кб)
       Взято с www.cs.rpi.edu/~goldberg/publications/papers-reversed.html
       Створено новий алгоритм для рішення задачі о найбільшій незалежній множині. Він виконується за час O(log⁴N) при реалізації на лінейній кількості EREW процесорів. Це перший детермінований алгоритм, що виконується за полілогаріфмічний час і виробка процесорного часу якого оптимізована до полілогарифмічного множителя.
  

• Bomze M., Budinich M., Pardalos P.M., Pelillo M. The maximum clique problem. in: Handbook of combinatorial optimization. – Adison-Wesley Publishing Company: 1998, 2410pp.[pdf - англійською] (535 кб)
       Взято с www.dsi.unive.it/~pelillo/papers/chapter-clique.ps.gz
       Задача о найбільшій клиці - класична задача комбінаторної оптимізації для якої знайшли важні застосування в різних галузях. В цій статті ми намагаємося навести огляд результатів, що пов'язані з алгоритмами, складностю та застосуваннями цієї задачі, і також наводимо доповнену бібліографію. Звичайно, ми посилаємось на попередні праці про подібні задачі.